function Point(){
  this.x = 0;
  this.y = 0;
  
  this.setPoint = function( x, y ) {
    this.x = x;
    this.y = y;
  };
}

function area( poly ){
  var res = 0;
  for( var i = 0; i < poly.length ; i++){
    res += cross( poly[i] ,poly[(i+1)%poly.length]);
  }
  return res / 2.0;
}

function vector( a, b ) {
  var res = new Point();
  
  res.setPoint( b.x - a.x, b.y - a.y);
  
  return res;
}

function mult( a, b ){
	return a.x * b.x + a.y * b.y;
}

function cross( a, b ){
  return a.x * b.y - a.y * b.x;
}

function ccw(  a,  b ,  c ){
  return cross( vector( a, b ) , vector( a, c ) );
}

function convexHull( points ){
  var eps = 1e11;
  points.sort( function( a, b ) {
    if (  a.x == b.x  ){
      if (a.y < b.y ) return 1;
      return -1;
    }
    if (a.x < b.x ) return 1;
    return -1;
  });
  
  
  var h =  new Array();
  var n = points.length;
  h.length = 2 * n;
  var k = 0;
  
  for( var i = 0; i < n ; i++ ){
    while( k >= 2 && ccw( h[ k - 2 ] , h[ k - 1 ], points[ i ] ) <= 0 ) k--;
    h[ k++ ] = points[ i ];
  }
  var tmp = k + 1;
  for( var i = n -2  ; i >= 0; i--){
    while( k >= tmp && ccw( h[ k - 2 ], h[ k - 1] , points[ i ] ) <= 0 ) k--;
    h[ k++ ] = points[ i ];
  }
  h.length = k;
       
  
  
  return h;
}

function getCenterMass( points ){

  var res = new Point();

  var cx = 0, cy = 0 ;
  
  for( var i = 0; i < points.length - 1 ; i++){
    var tmp = cross( points[ i ] , points[ (i + 1) ] );
    cx += (points[i].x + points[i+1].x) * tmp;
    cy += (points[i].y + points[i+1].y) * tmp;
  }
  var A = area( points );
  cx /= (6*A);
  cy /= (6*A);

  res.setPoint( cx, cy );
  
  return res;
}

function colinear( p, q, r ){

	var pq = vector( p , q );
	var rp = vector( r , p );
	
	if ( cross( pq , rp ) == 0 ) 
		if ( mult( pq, rp ) <= 0 ) 
			return 1;
    return 0;
}

function inPoly( k, p ) {
    var n= p.length;
    var cross=0;
    var r = new Point();
    var q  = new Point();
    for(var i = 1; i <= n; i++){
        q = p[i-1];
        r = p[i % n];
        if( colinear(k,q,r) ) return 2;
        if( q.y>r.y ) swap(q,r);
        if( q.y<k.y && r.y>=k.y && ccw(k,q,r) > 0) cross++;
    }
    return cross % 2;
}

